import collections
class Solution(object):
    def splitArray(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        n = len(nums)
        if n < 7:
            return False
        prefix = nums.copy()
        d = collections.defaultdict(set)
        out = [-1, -1, -1]
        for i in range(1, n):
            prefix[i] += prefix[i - 1]
            if prefix[i] not in d:
                d[prefix[i]] = {i}
            else:
                d[prefix[i]].add(i)

        def search(mode, num):
            if mode == 0:
                wait = d[prefix[-1] - num]
                if not wait:
                    return False
                else:
                    for index in wait:
                        if out[0] + 1 < index < n - 1:
                            out[2] = index
                            flag = search(1, num)
                            if flag:
                                return True
                    return False
            else:
                wait = d[prefix[out[2]] - nums[out[2]] - num]
                for index in wait:
                    if out[0] + 1 < index < out[2] - 1 and prefix[index] - prefix[out[0]] - nums[index] == num:
                        return True
                return False

        for i in range(1, n - 5):
            out[0] = i
            num = prefix[i] - nums[i]
            flag = search(0, num)
            if flag:
                return True
        return False


data = Solution()
nums = [1, 2, 1, 2, 1, 2, 1, 2]
print(data.splitArray(nums))
nums = [1, 2, 3, 3, 5, -1, 4, 6, 3]
print(data.splitArray(nums))